1. Field of the Invention
The present invention generally relates to methods and devices for generating random and/or pseudo-random numbers.
2. Background of the Invention
In many applications in the field of computers and other electronic devices there is a need for a physical source of true random numbers. Such applications include computer simulations of various probabilistic algorithms and processes, such as Monte Carlo numerical analysis, computer games, and cryptographic algorithms and protocols whose security relies on the ability to generate unpredictable secret keys. High-speed truly random sequences are also needed for setting up countermeasures against so-called side-channel attacks against specific electronic devices, particularly microelectronic devices, implementing security schemes, such as integrated chip cards; such countermeasures include for example random masking of cryptographic functions, as well as generation of secret keys for the encryption of internal links and memories in such devices.
The output of a Random Number Generator (RNG) is typically a binary sequence that, in principle, has to be unpredictable in the sense of the information theory. Equivalently stated, the RNG output should be statistically modeled as a purely random sequence, i.e., a sequence of mutually independent, uniformly distributed binary random variables (bits), with maximal possible entropy per bit. In particular, it should be computationally infeasible to distinguish the RNG output sequence from a purely random sequence or, equivalently, it should be computationally infeasible to predict the RNG output sequence.
As known in the art, random number sequences can be generated either by software or by hardware. Hardware-based RNGs are inherently capable of generating randomness of higher quality and speed, and those adapted to be implemented in the solid-state, semiconductor technology are preferable, because they can be more easily incorporated in Integrated Circuits (ICs), particularly digital ICs.
Hardware-based RNGs are known in the art that include analog electric/electronic elements, such as, for example, resistors and/or PN-junctions, and exploit as a source of randomness thermal noise and/or shot noise in such analog elements.
The presence of analog elements makes this type of RNGs difficult to be incorporated in digital ICs. Additionally, these RNGs are very sensitive to changes in temperature and other operating environment conditions, and this makes them vulnerable to physical attacks. Furthermore, the output sequence of these RNGs can be relatively slow. Consequently, in many practical electronic devices, including personal computers and integrated chip (IC) cards, analog hardware-based RNGs have not proven to be cost effective.
Another type of RNGs includes analog elements easier to be incorporated in digital ICs. For example, in U.S. Pat. No. 4,855,690 an integrated circuit RNG is disclosed, consisting of an analog oscillator exploited for varying the frequency of a higher-frequency Voltage-Controlled Oscillator (VCO). In particular, the analog oscillator is a free-running oscillator with triangular output signal that is used to control the VCO, which includes a nine-stage ring oscillator. To produce random digital values, the VCO output is sampled at a rate much smaller than the oscillation rate of the VCO, by means of a clock signal clocking a D-type flip-flop.
Several proposals have been made in the art for hardware-based RNGs that can be implemented by digital integrated circuits only, i.e., without using analog elements. These RNGs are typically based on free-running oscillators, implemented as ring oscillators, and exploit the phase jitter. As known in the art a ring oscillator is a circuit consisting of an odd number of (logic) inverters, connected in a circular cascade so as to form a ring. The ring connection and the odd number of inverters cause the circuit to oscillate; the number of inverters used in the ring determines the oscillation frequency, i.e., the frequency of the resulting signal. Accordingly, a ring oscillator can be equivalently represented by a circuit consisting of only one inverter, with appropriate delay.
For example, U.S. Pat. No. 4,641,102 describes an RNG in which a fast signal produced by a free-running oscillator is sampled by a slower clock through a D-type flip-flop and then XOR-ed into a number of shift registers circularly connected together and clocked by the same clock, where the XOR operation stands for the exclusive OR operation of binary values.
In another solution, described for example in U.S. Pat. No. 4,799,259, the outputs (binary oscillating signals) of a plurality of ring oscillators are combined with each other, using an XOR operation, and the combined output resulting from such combination is then sampled at a speed much lower than the oscillation frequency of the oscillators, by means of a system clock, through a D-type flip-flop; a so-called raw random binary sequence is thus obtained, having a certain degree of randomness due to the digital jitter, that is, due to unpredictable variations of frequency and relative phase shifts of the outputs of the different ring oscillators.
In particular, U.S. Pat. No. 4,799,259 discloses a random digital signal generator composed of an array of oscillator signal generators, particularly ring oscillators, each one operating at a different frequency; the outputs of the oscillators are XOR-ed together and then sampled at a much (at least 10-20 times) lower speed by a system clock through a D-type flip-flop.
The Applicant has observed that an important limitation of this type of RNGs is the considerable reduction in speed that is required in order to render them effective as a source of randomness. Moreover, the ring oscillators exhibit a tendency to lock onto each other and also on the system clock, which reduces the degree of randomness of the output sequence produced.
Another solution, described for example in U.S. Pat. No. 4,905,176, is to combine ring oscillators and Linear Feedback Shift Registers (LFSRs). LFSRs are commonly used as components of Pseudo-Random Number Generators (PRNGs). An LFSR is a cascade of D-type flip-flops, wherein the first flip-flop receives at its input a feedback signal corresponding to the output of the last flip-flop, possibly XOR-ed with the outputs of one or more other flip-flops in the cascade.
It is known in the art that binary sequences with a long period and good statistical properties can be produced by an LFSR operated in a synchronous manner according to a clock signal, and having appropriate feedback connections from the outputs of the intermediate flip-flops to the input of the first p-flop in the cascade. Nevertheless, an LFSR is however deterministic in nature and thus the output thereof is totally predictable; for this reason, the output sequences generated by LFSRs are qualified as pseudo-random, because they are not truly random, merely approximating some of the properties of true random numbers. The combination of LFSRs with ring oscillators introduces the necessary degree of randomness, allowing the circuit output to be non-deterministic; in other words, in such combinations of ring oscillators and LFSRs randomness is combined with pseudo-randomness.
In particular, ring oscillator signals can be used to clock the LFSRs; the output signal produced by the LFSRs then needs to be sampled at a lower speed by the system clock.
For example, U.S. Pat. No. 4,905,176 describes an embodiment of an RNG, wherein a free-running ring oscillator is used to drive/clock an LFSR, which is sampled at a lower speed by an external clock through a D-type flip-flop, thereby introducing randomly occurring deviations from the pseudo-random number sequence.
U.S. Pat. No. 4,905,176 also proposes a second embodiment of an RNG, wherein the output of a free-running oscillator is sampled at a lower speed by an external clock through a D-type flip-flop, the free-running oscillator being essentially a single LFSR, composed of a small number of delay elements, with a feedback signal produced by XOR gates, and which is operated asynchronously, without a clock signal. A delay element is implemented as a cascade of an even number of logic inverters. The oscillator would produce a pseudo-random output signal if operated synchronously from a non-zero initial state, but in the asynchronous operation it is expected to show elements of randomness due to unpredictable variations in the delay of delay elements.
The Applicant observes that the circuit is significantly flawed, because the state of all zeros is a fixed point in the state-transition diagram, which means that if the oscillator reaches such a state, which is very likely, it gets stuck in it and does not oscillate any more.
Still another example of an RNG involving a combination of ring oscillators that clock LFSRs is provided in the article by T. E. Tkacik “A Hardware Random Number Generator”, Cryptographic Hardware and Embedded Systems—CHES 2002, Lecture Notes in Computer Science, vol. 2523, pp. 450-453, 2002. A 32-bit hardware RNG is described consisting of two independent ring oscillators, respectively clocking an LFSR, of length 43, and a CASR (Cellular Automata Shift Register—a variation of an LFSR being a programmable linear cellular automaton), of length 37. The 32-bit output is obtained by bitwise XOR-ing two 32-bit blocks taken from the LFSR and from the CASR; the output is sampled only when a new number is required. The minimal sampling period should allow each of them to be clocked a number of times that is at least twice as large as its length, before producing the next output block.
However, a subsequent article by M. Dichtl, “How to predict the output of a hardware random number generator,” Cryptographic Hardware and Embedded System—CHES 2003, Lecture Notes in Computer Science, vol. 2779, pp. 181-188, 2003, proposes a practical attack on this RNG which allows predicting its output sequence. The attack is based on the fact that the two post-processing circuits are both linear, and that the only uncertainty to be guessed is the difference in the numbers of clocks for each of the circuits in a relatively short period of time. The attack can be prevented by reducing the output data rate by taking much less than 32 bits at a time or by increasing the minimal sampling period.
In an alternative solution, proposed for example in U.S. Pat. No. 6,240,432, ring oscillator output signals are XOR-ed with data inputs to particular flip-flops in LFSRs, clocked by a system clock slower than the ring oscillator frequencies. In this way, additional randomness is possibly introduced by effectively sampling multiple ring oscillator signals at various points in the LFSR circuit.
In particular, U.S. Pat. No. 6,240,432 discloses a RNG wherein an LFSR with additional XOR gates and a plurality of free-running (ring) oscillators are used to enhance randomness of the digital signals created at the outputs of the ring oscillators. In addition to the XOR gates used in the feedback path of the LFSR, additional XOR gates are also interposed between stages of the LFSR, and each of these additional XOR gates is connected to a high-frequency oscillator, so as to randomize the digital signals flowing between the LFSR stages. The frequencies of the oscillators are set so as not to be duplicated, and not to be a actor or multiple of one another; additionally, the oscillator frequencies are higher than the fluency of the system clock used to step the LFSR.
Another example of a digital RNG making use of a combination of ring oscillators and an LFSR is provided in US 2002/0156819: the RNG consists of an LFSR, a system clock driving the LFSR, and a plurality of free running oscillators connected to the input of the LFSR. In order to avoid interlocking of the oscillators and the system clock, the oscillators and the system clock have different oscillation frequency values, the greatest common divisor of which having the value one. The oscillator outputs are XOR-ed together, then sampled through a D-type flip-flop by the (slower) system clock, and then further XOR-ed into the data input of the LFSR clocked by the same system clock.
The Applicant has observed that another possible source of true randomness in digital semiconductor circuits is the meta-stability of RS (Reset-Set) latches and edge-triggered flip-flops based on RS latches. Namely, the output of such a flip-flop may become unpredictable if the input and clock signals are such that the characteristic setup and/or hold times are violated. For example, this may happen in a D-type flip-flop if the data input signal is forced to change at nearly the same time as the clock signal. The output signal then stabilizes on a random, typically biased value after a random amount of time (the bias being due to factors inherent to the physical implementation of the devices). The meta-stability of D-type flip-flops can possibly be exploited together with the jitter of ring oscillator signals by using D-type flip-flops for sampling the ring oscillator signals.
For example, U.S. Pat. No. 5,570,307 describes a digital RNG consisting of a plurality of free-running (ring) oscillators each of which is sampled by a common, much slower external clock through a separate D-type flip-flop and with their outputs XOR-ed together to form two output signals. These output signals are then XOR-ed into a circuit consisting of two shift registers with cross-feedback formed by applying XOR gates to individual stages of the registers, and this circuit is clocked by the same external clock. To improve on the randomness, some delay elements are inserted into the registers to possibly force the constituent D-type flip-flops into meta-stability, by intentionally violating the flip-flop set-up or hold time margins of incoming data relative to the jitter clock. Also, the external clock itself is produced with jitter.
Meta-stable behavior of flip-flops is also exploited in an RNG disclosed in U.S. Pat. No. 6,631,390, which describes several ways of exploiting the meta-stability of D-type flip-flops in order to obtain digital RNGs. They include detecting the meta-stability event and then using the corresponding output signal values or the timings between successive meta-stability events. The output of the flip-flop is compared to an input waveform to determine if the output signal does not match the input signal, indicating a meta-stable state. When a meta-stable state is detected, an output bit is provided as a random bit.